#define _CRT_SECURE_NO_WARNINGS 1

#include "singleList.h"

void singleListPrint(struct ListNode* phead)
{
	if (phead == NULL)
	{
		printf("NULL\n");
	}
	struct ListNode* tmp = NULL;
	tmp = phead;
	while (tmp != NULL)
	{
		printf("%d ", tmp->val);
		tmp = tmp->next;
	}
	printf("\n");
}

struct ListNode* detectCycle(struct ListNode* head)
{
	struct ListNode* fast = head;
	struct ListNode* slow = head;
	struct ListNode* tmp = head;
	while (fast != NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (fast == slow)
		{
			fast = head;
			while (fast != slow)
			{
				fast = fast->next;
				slow = slow->next;
			}
			return slow;
		}
	}
	return NULL;
}

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
	int numA = 1;
	int numB = 1;
	struct ListNode* tmpA = headA;
	struct ListNode* tmpB = headB;
	if (headA->next == NULL)
	{
		if (headB->next == NULL)
		{
			if (headA == headB)
			{
				return headA;
			}
		}
		while (headB)
		{
			if (headA == headB)
			{
				return headA;
			}
			else
			{
				headB = headB->next;
			}
		}
		return NULL;
	}
	if (headB->next == NULL)
	{
		if (headA->next == NULL)
		{
			if (headA == headB)
			{
				return headA;
			}
		}
		while (headA)
		{
			if (headA == headB)
			{
				return headA;
			}
			else
			{
				headA = headA->next;
			}
		}
		return NULL;
	}
	while (headA->next)
	{
		headA = headA->next;
		numA++;
	}
	headA = tmpA;
	while (headB->next)
	{
		headB = headB->next;
		numB++;
	}
	headB = tmpB;
	if (numA > numB)
	{
		int gap = (numA - numB);
		while (gap--)
		{
			headA = headA->next;
		}
		while (headA)
		{
			if (headA == headB)
			{
				return headA;
			}
			headA = headA->next;
			headB = headB->next;

		}
	}
	else
	{
		int gap = (numB - numA);
		while (gap--)
		{
			headB = headB->next;
		}
		while (headB)
		{
			if (headA == headB)
			{
				return headA;
			}
			headA = headA->next;
			headB = headB->next;

		}
	}
	return NULL;
}

struct ListNode* reverseList(struct ListNode* head)
{
	if (head == NULL)
	{
		return NULL;
	}
	if (head->next == NULL)
	{
		return head;
	}
	if (head->next->next == NULL)
	{
		struct ListNode* prev = head;
		struct ListNode* cur = head->next;
		prev->next = NULL;
		cur->next = prev;
		return cur;
	}
	struct ListNode* prev = head;
	struct ListNode* cur = head->next;
	struct ListNode* next = head->next->next;
	prev->next = NULL;
	while (next)
	{
		cur->next = prev;
		prev = next->next;
		next->next = cur;
		if (prev == NULL)
		{
			return next;
		}
		cur = prev->next;
		prev->next = next;
		if (cur == NULL)
		{
			return prev;
		}
		next = cur->next;
		cur->next = prev;
		if (next == NULL)
		{
			return cur;
		}
	}
	return cur;
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	struct ListNode* cur1 = list1;
	struct ListNode* cur2 = list2;
	struct ListNode* newhead = (struct ListNode*)malloc
	(sizeof(struct ListNode));
	newhead->val = 0;
	newhead->next = NULL;
	struct ListNode* tmp = newhead;
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}
	while (1)
	{
		if (!(cur1 == NULL || cur2 == NULL))
		{
			if (cur1->val <= cur2->val)
			{
				struct ListNode* newnode = (struct ListNode*)malloc
				(sizeof(struct ListNode));
				newnode->val = cur1->val;
				newhead->next = newnode;
				newhead = newhead->next;
				newhead->next = NULL;
				cur1 = cur1->next;
			}
			else
			{
				struct ListNode* newnode = (struct ListNode*)malloc
				(sizeof(struct ListNode));
				newnode->val = cur2->val;
				newhead->next = newnode;
				newhead = newhead->next;
				newhead->next = NULL;
				cur2 = cur2->next;
			}
		}
		if (cur1 == NULL)
		{
			newhead->next = cur2;
			return tmp->next;
		}
		if (cur2 == NULL)
		{
			newhead->next = cur1;
			return tmp->next;
		}
	}
}

struct ListNode* partition(struct ListNode* pHead, int x) 
{
	struct ListNode* cur = pHead;
	struct ListNode* frontList = (struct ListNode*)
						malloc(sizeof(struct ListNode));
	struct ListNode* behindList = (struct ListNode*)
						malloc(sizeof(struct ListNode)); 
	struct ListNode* tmp1 = frontList;
	tmp1->val = 0;
	tmp1->next = NULL;
	struct ListNode* tmp2 = behindList;
	tmp2->val = 0;
	tmp2->next = NULL;
	while (cur)
	{
		struct ListNode* newnode = (struct ListNode*)
						malloc(sizeof(struct ListNode));
		newnode->val = cur->val;
		newnode->next = NULL;
		if (cur->val < x)
		{
			tmp1->next = newnode;
			tmp1 = tmp1->next;
		}
		else
		{
			tmp2->next = newnode;
			tmp2 = tmp2->next;
		}
		cur = cur->next;
	}
	tmp1->next = behindList->next;
	return frontList->next;
}